package com.base.leetcode;

import java.util.Arrays;

/**
 * @Author: hdhao
 * @Create: 2023/3/30 - 23:08
 * @Version: v1.0
 */
//合并两个有序数组
public class Leetcode88 {


    //方法1 递归实现
    public static void merge1(int[] a1,int i,int iEnd,int j,int jEnd,int[] a2,int k){
        if (i >iEnd){
            System.arraycopy(a1,j,a2,k,jEnd-j+1);
            return;
        }
        if (j > jEnd){
            System.arraycopy(a1,i,a2,k,iEnd-i+1);
            return;
        }
        if (a1[i] < a1[j]){
            a2[k] = a1[i];
            merge1(a1,i+1,iEnd,j,jEnd,a2,k+1);
        }else {
            a2[k] = a1[j];
            merge1(a1,i,iEnd,j+1,jEnd,a2,k+1);
        }
    }
    //方法2 指针实现
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n - 1;
        int index1 = m - 1;
        int index2 = n - 1;
        while(index1 >= 0 && index2 >= 0) {
            if(nums1[index1] >= nums2[index2]) {
                nums1[k] = nums1[index1];
                k--;
                index1--;
            } else {
                nums1[k] = nums2[index2];
                k--;
                index2--;
            }
        }
        while(index1 >= 0) {
            nums1[k] = nums1[index1];
            k--;
            index1--;
        }
        while(index2 >= 0) {
            nums1[k] = nums2[index2];
            k--;
            index2--;
        }
    }

    public static void main(String[] args) {
        int[] a1 = {1,2,3,0,0,0};
        int[] a2 = {2,5,6};
        merge(a1,3,a2,3);
        System.out.println(Arrays.toString(a1));
        System.out.println(Arrays.toString(a2));
    }
}
